#include "DoubleLinkList.h"
// #include "DynamicArray.h"

DoubleLinkList::DoubleLinkList():size(0)
{
    head = tail = new Node(0);
    Free = nullptr;
    Compare = nullptr;
    Print = nullptr;

}

DoubleLinkList::DoubleLinkList(const DoubleLinkList &list)
{
    size = list.size;
    head = tail = new Node(0);
    Node *tp = head;
    Node *travelPoint = list.head->next;
    Copy = list.Copy;
    Free = list.Free;
    Print =list.Print;
    while(travelPoint != nullptr)
    {
        Node *newNode = new Node(travelPoint->value);
        if(Free != nullptr)
            newNode->value = Copy(newNode->value);
        tp->next = newNode;
        tp->next->prev = tp;
        tp = tp->next;
        travelPoint = travelPoint->next;
    }
    tail = tp;
}

DoubleLinkList &DoubleLinkList::operator=(const DoubleLinkList &list)
{
    while(head != nullptr)
    {
        Node *nextNode = head->next;//下一个节点
        if(Free && nextNode)
            Free(nextNode->value);
        delete head;
        head = nextNode;
    }
    tail = nullptr;
    size = list.size;
    head = tail = new Node(0);
    Copy = list.Copy;
    Free = list.Free;
    Print =list.Print;
    Node *tp = head;
    Node *travelPoint = list.head->next;
    while(travelPoint != nullptr)
    {
        Node *newNode = new Node(travelPoint->value);
        if(Free != nullptr)
            newNode->value = Copy(newNode->value);
        tp->next = newNode;
        tp->next->prev = tp;
        tp = tp->next;
        travelPoint = travelPoint->next;
    }
    tail = tp;
    return *this;
}

DoubleLinkList::~DoubleLinkList()
{
    while(head != nullptr)
    {
        Node *nextNode = head->next;//下一个节点
        if(Free && nextNode)
            Free(nextNode->value);
        delete head;
        head = nextNode;
    }
    tail = nullptr;
}

void DoubleLinkList::InsertTail(const ElementType& element)
{
    Node *newNode = new Node(element);
    tail->next = newNode;
    newNode->prev = tail;
    tail = newNode;
    size++;

    if(Free != nullptr)
        newNode->value = Copy(newNode->value);
}

void DoubleLinkList::InsertByIndex(size_t index, const ElementType &element)
{
    if(index >= size)//杜绝尾插
    {
        std::cout<<"位置非法\n";
        return;
    }
    Node *travelPoint = head;
    for(size_t i = 0;i < index ;i++)
    {
        travelPoint = travelPoint->next;
    }
    Node *newNode = new Node(element);
    newNode->next = travelPoint->next;
    newNode->prev = travelPoint;

    travelPoint->next = newNode;
    newNode->next->prev =newNode;
    size++;
    if(Free != nullptr)
        newNode->value = Copy(newNode->value);
}

void DoubleLinkList::RemoveByIndex(size_t index)
{
    if(index >= size)
    { 
        std::cout<<"删除位置非法\n";
        return;
    }
    Node *travelPoint = head;
    for(size_t i = 0;i < index;i++)
        travelPoint = travelPoint->next;
    Node *freeNode = travelPoint->next;
    travelPoint->next = freeNode->next;
    if(freeNode->next != nullptr)
        freeNode->next->prev = travelPoint;
    else if(freeNode->next == nullptr)
        tail = freeNode->prev;
    if(Free)
        Free(freeNode->value);
    delete freeNode;
    size--;
}

void DoubleLinkList::RemoveByElemnt(const ElementType &element)
{
    Node *travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        if(Compare(travelPoint->next->value,element) == 0)
        {
            Node *freeNode = travelPoint->next;
            travelPoint->next = freeNode->next;
            if(freeNode->next != nullptr)
                freeNode->next->prev = travelPoint;
            else if(freeNode->next == nullptr)
                tail = freeNode->prev;
            if(Free)
                Free(freeNode->value);
            delete freeNode;
            size--;
        }
        else
            travelPoint = travelPoint->next;
    }
}

DoubleLinkList::ElementType *DoubleLinkList::FindByIndex(size_t index)
{
    if(index >= size)
        return nullptr;
    Node *travelPoint = head->next;
    for(size_t i = 0; i < index; i++)
        travelPoint = travelPoint->next;
    return &travelPoint->value;
}

// DARRAY::DynamicArray DoubleLinkList::FindByElement(const ElementType &element)
// {
//     DARRAY::DynamicArray array;
//     Node *travelPoint = head->next;
//     while(travelPoint != nullptr)
//     {
//         if(travelPoint->value == element)
//         {
//             array.InsertTail(travelPoint->value);
//         }
//         travelPoint = travelPoint->next;
//     }
//     return array;
// }

void DoubleLinkList::UpdateByIndex(size_t index, const ElementType &element)
{
    if(index >= size)
    {
        std::cout<<"修改位置非法\n";
        return;
    }
    Node *travelPoint = head->next;
    for(size_t i = 0;i < index;i++)
        travelPoint = travelPoint->next;
    if(Free)
    {
        Free(travelPoint->value);
        travelPoint->value = Copy(element);
    }
    else
        travelPoint->value = element;
}

void DoubleLinkList::UpdateByElement(const ElementType &oldvalue, const ElementType &newvalue)
{
    Node *travelPoint = head->next;
    while(travelPoint != nullptr)
    {
        if(Compare(travelPoint->value,oldvalue) == 0)
        {
            if(Free)
            {
                Free(travelPoint->value);
                travelPoint->value = Copy(newvalue);
            }
            else
                travelPoint->value = newvalue;
        }
        travelPoint = travelPoint->next;
    }
}

void DoubleLinkList::FastSort(Node *start, Node *end)
{
    if(start == end)
        return;
    Node *left = start;
    Node *right = end;
    ElementType temp = start->value;
    while(left != right)
    {
        while(Compare(right->value,temp) > 0 && left != right)
            right = right->prev;
        if(left != right)
        {
            left->value = right->value;
            left = left->next;
        }
        while(Compare(left->value,temp) < 0 && left != right)
            left = left->next;
        if(left != right)
        {
            right->value = left->value;
            right = right->prev;
        }  
    }
    left->value = temp;
    if(left != start)
        FastSort(start,left->prev);
    if(right != end)
        FastSort(right->next,end);
        //终止条件
    // if(start == end)
    //     return;
    // Node *temp = start;//基准值指针
    // Node *slow = start;//慢指针
    // Node *fast = start->next;
    // while(fast != end)
    // {
    //     //快指针指向的值比基准值小
    //     if(Compare(fast->value,temp->value) < 0)
    //     {
    //         slow = slow->next;
    //         std::swap(slow->value,fast->value);
    //         //slow = slow->next;
    //     }
    //     fast = fast->next;
    // }
    // std::swap(temp->value,slow->value);//将基准值归位
    // FastSort(start,slow);//[start,slow)
    // FastSort(slow->next,end);

}

void DoubleLinkList::Sort()
{
    FastSort(head->next,tail);
}

DoubleLinkList DoubleLinkList::Merge(const DoubleLinkList &list)
{
    DoubleLinkList result;
    result.Copy = list.Copy;
    result.Free = list.Free;
    Node* first = head->next;
    Node* second = list.head->next;
    while(first  && second )
    {
        if(Compare(first->value,second->value) < 0)
        {
            result.InsertTail(first->value);
            first = first->next;
        }
        else 
        {
            result.InsertTail(second->value);
            second = second->next;
        }
    }
    while(first)
    {
        result.InsertTail(first->value);
        first = first->next;
    }
    while(second)
    {
        result.InsertTail(second->value);
        second = second->next;
    }
    return result;
}

void DoubleLinkList::show()
{
    std::cout<<"size : "<<size<<std::endl;
    Node *travelPoint = head->next;
    while(travelPoint != nullptr)//链表还没有结束
    {
        //std::cout<<travelPoint->next<<std::endl;
        Print(travelPoint->value);
        travelPoint = travelPoint->next;//遍历指针往后走
    }
    std::cout<<std::endl;

    travelPoint = tail;
    while(travelPoint != head)//链表还没有结束
    {
        //std::cout<<travelPoint->next<<std::endl;
        Print(travelPoint->value);
        travelPoint = travelPoint->prev;//遍历指针往后走
    }   
    std::cout<<std::endl;
}

